home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 15949 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.6 KB
  1. Path: in2.uu.net!novia!usenet
  2. From: srwillrd@novia.net (William E. Kempf)
  3. Newsgroups: comp.lang.c++,comp.lang.c,comp.os.msdos.programer,comp.os.ms-windows.programmer.misc
  4. Subject: Re: fastest code
  5. Date: Mon, 08 Apr 1996 23:23:22 GMT
  6. Organization: Novia Internetworking <> 28.8kbps dialup; 402/390-2NET
  7. Message-ID: <31698acd.361838756@204.248.25.97>
  8. References: <316112A2.7D37@public.sta.net.cn> <31611AC9.7DE1@wight.hursley.ibm.com> <3162c21a.6084138@204.248.25.97> <31641DE2.31D4@halcyon.com> <31658942.99299605@204.248.25.97> <4k9g04$4ov@news1.mnsinc.com>
  9. NNTP-Posting-Host: 167.16.65.84
  10. X-Newsreader: Forte Agent .99e/32.201
  11.  
  12. huang@mnsinc.com (Szu-Wen Huang) wrote:
  13.  
  14. :William E. Kempf (srwillrd@novia.net) wrote:
  15. :
  16. :: Ok, my cutsy remark has confused several people, so I will explain.
  17. :: In computer science, algorithms (and this will apply to the final
  18. :: machine code generated by a compiler) are evaluated for speed in a
  19. :: system independant way, through a formula known as Big-O notation.  So
  20. :: code is not said to be faster just because it is running on a faster
  21. :: machine.  The executable program may be faster, but the underlying
  22. :: code may not be.  All kinds of things can effect this, such as wether
  23. :: or not the compiler moves variable declarations outside of loops, etc.
  24. :
  25. :Unfortunately, the big-O analysis of algorithms do not tell you of
  26. :the algorithm's speed, rather, it shows the relationship between
  27. :input size and execution time.  An O(n^2) algorithm may run faster
  28. :than an O(n) algorithm for all practical sizes of n.
  29. :
  30. :: The original question was looking for this kind of information (even
  31. :: if the poster does not understand Big-O, which I don't know if he did
  32. :: or not).  He wants to know what compiler will best optimize the
  33. :: machine language code generated for a specific OS and computer
  34. :: architecture.
  35. :
  36. :Optimizations have little to do with time complexities as well.  A
  37. :compiler today is not likely to change an O(n^2) algorithm into an
  38. :O(n) algorithm simply by optimizing the code, though an O(n) algorithm
  39. :might be optimized into an O(1) algorithm if you're talking about a
  40. :truly dumb programmer ;).
  41.  
  42. Point taken.  That's the second time I've stated something in the
  43. Usenet in as many days that is incorrect (or incomplete).  In both
  44. cases I should have known better, but didn't think things through.
  45.  
  46. Oh well, math is not my strong suit, and Big-O give me no end of
  47. problems well getting my degree...
  48.  
  49. -----
  50. William E. Kempf          : http://www.novia.net/~srwillrd
  51. "Sir Willard"             : mailto:srwillrd@novia.net (home)
  52. Knight of the Ascii Table : mailto:wekempf@marlton.1dc.com (work)
  53.